package com.google.sky.ai.simple;

import com.google.sky.Board;
import com.google.sky.MoveResolver;
import com.google.sky.Position;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * Implementation of alpha-beta minimax algorithm.
 *
 * @author sslautin
 * @version 1.0 18.11.2014
 */
public class MoveResolverImpl implements MoveResolver {

    // team name
    private static final String RESOLVER_NAME = "Computer";

    // int representation of board positions
    private static final int EMPTY_P = Heuristic.EMPTY_P;
    private static final int MINE_P = Heuristic.MINE_P;
    private static final int NOT_MINE_P = Heuristic.NOT_MINE_P;

    // search depth of the minimax algorithm
    private static final int SEARCH_DEPTH = 3;
    // amount of first sorted scored moves to check
    private static final int SEARCH_WIDTH = 5;

    // alpha-beta min and max values
    private static final int HEURISTIC_MIN_VALUE = Heuristic.MIN_VALUE;
    private static final int HEURISTIC_MAX_VALUE = Heuristic.MAX_VALUE;

    // init random for select one of a equal positions
    private static final Random RANDOM = new Random();

    @Override
    public Position nextStep(final Board board) {

        Position nextStep;

        final int boardWidth = board.getWidth();
        final int boardHeight = board.getHeight();
        final int[][] boardAsArray = getBoardAsArray(board);

        if (isBoardClear(boardAsArray)) {
            nextStep = findStartPosition(boardWidth, boardHeight);
        } else if (isMineFirstTurn(boardAsArray)) {
            nextStep = findSecondPosition(boardAsArray);
        } else {
            nextStep = findBestNextPosition(boardAsArray);
        }

        return nextStep;
    }

    @Override
    public String getTeamName() {

        return RESOLVER_NAME;
    }

    /**
     * Returns 2D int array representation of the board.
     */
    private int[][] getBoardAsArray(final Board board) {

        final int x = board.getWidth();
        final int y = board.getHeight();
        final int[][] boardAsArray = new int[x][y];

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                final Position position = board.getPositionAt(i, j);
                if (position.isEmpty()) {
                    boardAsArray[i][j] = EMPTY_P;
                } else if (position.isMine()) {
                    boardAsArray[i][j] = MINE_P;
                } else {
                    boardAsArray[i][j] = NOT_MINE_P;
                }
            }
        }

        return boardAsArray;
    }

    /**
     * Checks if nobody has a turn yet.
     */
    private boolean isBoardClear(final int[][] board) {

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[x].length; y++) {
                if (board[x][y] != EMPTY_P) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Checks if there are no mine stones on the board yet.
     */
    private boolean isMineFirstTurn(final int[][] board) {

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[x].length; y++) {
                if (board[x][y] == MINE_P) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Returns custom position.
     */
    private Position definePosition(final int x, final int y, final boolean isMine, final boolean isEmpty) {

        return new Position() {
            @Override
            public int getX() {
                return x;
            }

            @Override
            public int getY() {
                return y;
            }

            @Override
            public boolean isMine() {
                return isMine;
            }

            @Override
            public boolean isEmpty() {
                return isEmpty;
            }
        };
    }

    /**
     * Returns the center of the board.
     */
    private Position findStartPosition(final int boardWidth, final int boardHeight) {

        return definePosition(boardWidth / 2, boardHeight / 2, true, false);
    }

    /**
     * Returns the position near the center of the board.
     */
    private Position findSecondPosition(final int[][] board) {

        final List<Position> positions = new ArrayList<Position>();
        final int x = board.length / 2;
        final int y = board[0].length / 2;

        for (int i = x - 1; i <= x + 1; i++) {
            for (int j = y - 1; j <= y + 1; j++) {
                if (board[i][j] == EMPTY_P) {
                    positions.add(definePosition(i, j, true, false));
                }
            }
        }

        return positions.get(RANDOM.nextInt(positions.size()));
    }

    /**
     * Returns possibly best position for next turn.
     * Uses alpha-beta minimax algorithm for finding such position.
     */
    private Position findBestNextPosition(final int[][] board) {

        final List<Position> bestPositions = new ArrayList<Position>();
        int bestScore = HEURISTIC_MIN_VALUE;

        final List<ScoredMove> moves = getOrderedMoves(board, true);
        for (int i = 0; i < SEARCH_WIDTH && i < moves.size(); i++) {
            final ScoredMove move = moves.get(i);
            final int x = move.x;
            final int y = move.y;

            if (move.getScore() == HEURISTIC_MAX_VALUE) {
                return definePosition(x, y, true, false);
            }

            board[x][y] = MINE_P;
            final int score = alphaBeta(board, SEARCH_DEPTH - 1, HEURISTIC_MIN_VALUE, HEURISTIC_MAX_VALUE, false);
            board[x][y] = EMPTY_P;

            if (score == HEURISTIC_MAX_VALUE) {
                return definePosition(x, y, true, false);
            }

            if (score == bestScore) {
                bestPositions.add(definePosition(x, y, true, false));
            } else if (score > bestScore) {
                bestPositions.clear();
                bestPositions.add(definePosition(x, y, true, false));
                bestScore = score;
            }
        }

        if (bestScore == HEURISTIC_MIN_VALUE) {
            final ScoredMove finalMove = moves.get(0);
            return definePosition(finalMove.x, finalMove.y, true, false);
        }

        if (bestPositions.isEmpty()) {
            return getRandomPosition(board);
        } else {
            return bestPositions.get(RANDOM.nextInt(bestPositions.size()));
        }
    }

    /**
     * Randomly selects empty position on the board.
     */
    private Position getRandomPosition(final int[][] board) {

        final List<Position> positions = new ArrayList<Position>();

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                if (board[x][y] == EMPTY_P) {
                    positions.add(definePosition(x, y, true, false));
                }
            }
        }

        if (positions.isEmpty()) {
            return null;
        } else {
            return positions.get(RANDOM.nextInt(positions.size()));
        }
    }

    /**
     * Alpha-beta minimax search algorithm.
     */
    private int alphaBeta(
        final int[][] node,
        final int depth,
        final int alpha,
        final int beta,
        final boolean maximizingPlayer
    ) {

        if (depth == 0) {
            return Heuristic.calculateHeuristicValue(node);
        }

        if (maximizingPlayer) {
            int bestScore = alpha;

            final List<ScoredMove> moves = getOrderedMoves(node, true);
            for (ScoredMove move : moves) {
            //for (int i = 0; i < SEARCH_WIDTH && i < moves.size(); i++) {
              //  final ScoredMove move = moves.get(i);
                final int x = move.x;
                final int y = move.y;

                if (move.getScore() == HEURISTIC_MAX_VALUE) {
                    return HEURISTIC_MAX_VALUE;
                }

                node[x][y] = MINE_P;
                //α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
                final int score = alphaBeta(node, depth - 1, bestScore, beta, false);
                bestScore = Math.max(bestScore, score);
                node[x][y] = EMPTY_P;

                //if β ≤ α -> break
                if (beta <= bestScore) {
                    return bestScore;
                }
            }

            return bestScore;
        } else {
            int bestScore = beta;

            final List<ScoredMove> moves = getOrderedMoves(node, false);
            for (ScoredMove move : moves) {
            //for (int i = 0; i < SEARCH_WIDTH && i < moves.size(); i++) {
              //  final ScoredMove move = moves.get(i);
                final int x = move.x;
                final int y = move.y;

                if (move.getScore() == HEURISTIC_MIN_VALUE) {
                    return HEURISTIC_MIN_VALUE;
                }

                node[x][y] = NOT_MINE_P;
                //β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
                final int score = alphaBeta(node, depth - 1, alpha, bestScore, true);
                bestScore = Math.min(bestScore, score);
                node[x][y] = EMPTY_P;

                //if β ≤ α -> break
                if (bestScore <= alpha) {
                    return bestScore;
                }
            }

            return bestScore;
        }
    }

    /**
     * Returns all possible moves in heuristic score order.
     */
    private List<ScoredMove> getOrderedMoves(final int[][] board, final boolean mine) {

        List<ScoredMove> moves = new ArrayList<ScoredMove>();

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                if (board[x][y] == EMPTY_P) {
                    if (mine) {
                        board[x][y] = MINE_P;
                        final int score = Heuristic.calculateHeuristicValue(board);
                        board[x][y] = EMPTY_P;
                        moves.add(ScoredMoveFactory.createScoredMove(x, y, true, score));
                    } else {
                        board[x][y] = NOT_MINE_P;
                        final int score = Heuristic.calculateHeuristicValue(board);
                        board[x][y] = EMPTY_P;
                        moves.add(ScoredMoveFactory.createScoredMove(x, y, false, score));
                    }
                }
            }
        }

        Collections.sort(moves);
        Collections.reverse(moves);

        return moves;
    }
}
